package com.faiz.algorithm;

import java.util.Random;

public class QuickSort {
    //我们决定使用随机数来防止极端情况的出现
    Random random = new Random(5);
    public int generateRandom(int min, int max) {
        return random.nextInt(max - min + 1) + min;
    }
    public int[] solution(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        quickSort(nums, 0, nums.length - 1);

        return nums;
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start == end) {
            return;
        }
        int index = partition(nums, start, end);
        if (index > start) {
            quickSort(nums, start, index - 1);
        }
        if (index < end) {
            quickSort(nums, index + 1, end);
        }
    }

    public int partition(int[] nums, int start, int end) {
        int index = generateRandom(start, end);
        swap(nums, start, index);
        int i = start;
        int j = end;
        boolean reverseFlag = true;//控制方向
        while (i != j) {
            if (reverseFlag) {
                if (nums[j] < nums[i]) {
                    swap(nums, i, j);
                    reverseFlag = false;
                } else {
                    j--;
                }
            } else {
                if (nums[i] > nums[j]) {
                    swap(nums, i, j);
                    reverseFlag = true;
                } else {
                    i++;
                }
            }
        }
        return i;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}



